package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-28 18:37
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class N皇后 {
    public boolean[] colUsed;
    public Map<Integer, Boolean> rightUsed = new HashMap<>();;
    public Map<Integer, Boolean> leftUsed = new HashMap<>();;
    public int n;
    public List<Integer> ans = new ArrayList<>(); // 存放每一次递归完成后的答案
    public List<List<Integer>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        colUsed = new boolean[n];
        for (int i = 0; i < n; i++) {
            colUsed[i] = false;
        }
        this.n = n;
        dfs(0);

        List<List<String>> questionResult = new ArrayList<>();
        for (List<Integer> list : result) {
            // 有答案次循环
            List<String> tempResult = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                Integer Qindex = list.get(i);
                for (int j = 0; j < n; j++) {
                    if (j!=Qindex) sb.append(".");
                    else sb.append("Q");
                }
                tempResult.add(sb.toString());
                sb = new StringBuilder();
            }
            questionResult.add(tempResult);
        }
        return questionResult;
    }

    /**
     * for 循环中的j代表的是每一列
     * @param i 每一行
     */
    private void dfs(int i) {
        if (i == n) {
            // 到达了边界条件
            List<Integer> temp = new ArrayList<>(ans); // 拷贝一份
            result.add(temp);
        }

        for (int j = 0; j < n; j++) { // 每一层都进行一次选择
            if (!rightUsed.containsKey(i-j)) rightUsed.put(i-j,false);
            if (!leftUsed.containsKey(i+j)) leftUsed.put(i+j,false);
            if (!colUsed[j] && !rightUsed.get(i-j) && !leftUsed.get(i+j)) { // 如果没有用过
                colUsed[j] = true; // 表示用过
                rightUsed.put(i-j,true);
                leftUsed.put(i+j,true);
                ans.add(j);
                dfs(i+1);
                colUsed[j] = false;
                rightUsed.put(i-j,false);
                leftUsed.put(i+j,false);
                ans.remove(ans.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new N皇后().solveNQueens(4));
    }

}
